package com.hy.study.recursion;

/**
 * 8皇后问题
 */
public class Queue8 {
    private int max=8;//一共有多少个皇后
    private int[] arr=new int[max];//用于保存防止皇后的结果
    private static  int count=0;
    private static int judgeCount=0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d种解法\n",count);
        System.out.printf("一共判断了%d次",judgeCount);

    }

    /**
     * 放置皇后
     * @param n
     */
    private void check(int n){
        if(n==max){//所有的皇后放好了
            printf();
            count++;
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前皇后n,放到该行的第一列
            arr[n]=i;
            //判断当放置第n个皇后到i列时，是否冲突
            if(judge(n)){//不冲突
                //接着放n+1个皇后
                check(n+1);
            }
            //如果冲突，就继续执行array[n]=i,即将第n个皇后，放置在本行的后移一个位置
        }
    }

    /**
     * 放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
     *
     */
    private boolean judge(int n){
        judgeCount++;
        for (int i = 0; i < n; i++) {
            //同一列 和同一条斜线
            if(arr[i]==arr[n]|| Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;

            }
        }
        return true;
    }

    /**
     * 打印结果
     */
    private void printf(){
        for(int i=0;i<max;i++){
            System.out.printf("%d\t",arr[i]);
        }
        System.out.println("");
    }



}
